// 思路：以二分搜索为基本思路
// 简单来说：1. nums[0] <= nums[mid] (0 到 mid 不包含旋转) 且 nums[0] <= target <= nums[mid]
// 2. nums[mid] < nums[0] (0 到 mid 包含旋转) target <= nums[mid] < nums[0] (target 在旋转位置到 mid 之间)
// 3. nums[mid] < nums[0] nums[mid] < nums[0] <= target (target 在 0 到旋转位置之间)
// 其它情况向后规约
// 也就是说，nums[mid] < nums[0] nums[0] < target target > nums[mid] 三项为真或者只有一项为真时向后规约

// 注意到原数组为有限制的有序数组（除了在某个点会突然下降外均为升序数组）
// if nums[0] < nums[i] 那么 nums[0] 到 nums[i] 为有序数组，那么当 nums[0] <= target <= nums[i]
// 此时我们应该在 0 到 i 范围内查找
// if nums[i] < nums[0] 那么在 0 到 i 区间的某个点处发生了下降（旋转），那么 i + 1 到最后一个数字的
// 区间为有序数组，并且所有的数字都是小于 nums[0] 且大于 nums[i]，
// 当 target 不属于 nums[0] 到 nums[i]时
// (target <= nums[i] < nums[0] or nums[i] < nums[0] <= target)，我们应该在 0 到 i 区间内查找
//  解题关键是 target 在哪个数组的一边内
var search = function (nums, target) {
  let low = 0;
  let high = nums.length - 1;
  while (low < high) {
    let mid = (low + high) >> 1;
    if ((nums[0] > nums[mid]) ^ (target > nums[mid]) ^ (target < nums[0])) {
      low = mid + 1;
    } else {
      hight = mid;
    }
  }
  return low == high && nums[low] === target ? low : -1;
};

var search = function (nums, target) {
  let low = 0;
  let high = nums.length - 1;
  while (low <= high) { // 考虑只有 1 个元素的情况
    let mid = (low + high) >> 1;
    if (nums[mid] === target) {
      return mid;
    }
    if (nums[low] <= nums[mid]) { // [left, mid] 连续递增
      if (nums[low] <= target && target < nums[mid]) { // low 可能是 target
        high = mid - 1;
      } else {
        low = mid + 1;
      }
    } else { // [mid, right] 连续递增
      if (nums[mid] < target && target <= nums[high]) {
        low = mid + 1;
      } else {
        high = mid - 1;
      }
    }
  }
  return -1;
};
